package com.lw.leetcode.greedy.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1040. 移动石子直到连续 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/5 17:50
 */
public class NumMovesStonesII {

    public static void main(String[] args) {
        NumMovesStonesII test = new NumMovesStonesII();

        // [1,2]
//        int[] arr = {7,4,9};

        // [2,3]
//        int[] arr = {6,5,4,3,10};

        // [0,0]
        int[] arr = {100,101,104,102,103};

        int[] ints = test.numMovesStonesII(arr);
        System.out.println(Arrays.toString(ints));
    }


    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int length = stones.length;
        int index = 0;
        int[] arr = new int[2];
        arr[0] = Integer.MAX_VALUE;
        for (int i = 1; i < length; i++) {
            arr[1] += (stones[i] - stones[i - 1] - 1);
        }
        arr[1] -= Math.min(stones[1]- stones[0] - 1, stones[length - 1]- stones[length - 2] - 1);
        for (int i = 0; i < length; i++) {
            int st = stones[i];
            int end = st + length - 1;
            while (index != length && stones[index] <= end) {
                index++;
            }
            if (index == length) {
                if (stones[index - 1] == end) {
                    arr[0] = Math.min(arr[0], i);
                }
                arr[0] = arr[0] == Integer.MAX_VALUE ? 0 : arr[0];
                return arr;
            }
            if (i == 0 && length - index == 1) {
                continue;
            }
            arr[0] = Math.min(arr[0], i + length - index);
        }
        arr[0] = arr[0] == Integer.MAX_VALUE ? 0 : arr[0];
        return arr;
    }

}
